package com.leetcode.sort.basic_sort;

import java.util.Random;

/**
 * @author Dennis Li
 * @date 2020/9/9 23:39
 */
public class BubbleSort extends Sort {

    public static void main(String[] args) {
        int[] res = new Random().ints(10, 0, 100).toArray();
        sort2(res);
        System.out.println(isSorted(res));
    }

    // 原始
    public static void sort(int[] nums) {
        for (int i = nums.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j + 1, j);
                }
            }
        }
    }

    // 优化2版
    public static void sort1(int[] nums) {
        for (int i = nums.length - 1; i > 0; i--) {
            boolean flag = true;
            for (int j = 0; j < i; j++) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j + 1, j);
                    flag = false;
                }
            }
            // 优化 -- 如果一次遍历完没有交换顺序，那么直接退出
            if (flag) break;
        }
    }

    // 最终优化版本
    public static void sort2(int[] nums) {
        int len = nums.length - 1, tempPos = 0;

        for (int i = 0; i < nums.length - 1; i++) {
            boolean flag = false;
            for (int j = 0; j < len; j++) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j, j + 1);
                    tempPos = j;
                    flag = true;
                }
            }
            len = tempPos;
            if (!flag) break;
        }
    }

    static class Solution {
        public static void main(String[] args) {
            for (int i = 0; i < 10; i++) {
                int[] res = new Random().ints(10, 0, 100).toArray();
                sort2(res);
                System.out.println(isSorted(res));
            }
        }

        public static void sort(int[] nums) {
            int len = nums.length - 1, tempPos = len;
            for (int i = 0; i < nums.length; i++) {
                boolean flag = true;
                for (int j = 0; j < len; j++) {
                    if (nums[j] > nums[j + 1]) {
                        swap(nums, j, j + 1);
                        flag = false;
                        tempPos = j;
                    }
                }
                if (flag) break;
                len = tempPos;
            }
        }
    }

}
